package com.heyqing;

import java.util.*;
import java.util.stream.Collectors;

import static com.heyqing.LinkTools.*;
import static com.heyqing.TreeTools.*;

/**
 * ClassName:Enter
 * Package:com.heyqing
 * Description:
 *
 * @Date:2024/10/16
 * @Author:Heyqing
 */
public class Enter {
    public static void main(String[] args) {
        Enter enter = new Enter();
//        mergeKListsTest(enter);
//        numTreesTest(enter);
//        swapPairsTest(enter);
//        deleteDuplicatesTest(enter);
//        reverseKGroupTest(enter);
//        rotateRightTest(enter);
//        partitionTest(enter);
//        reverseBetweenTest(enter);
//        detectCycleTest(enter);
//        lengthAfterTransformationsTest(enter);
//        longestContinuousSubstringTest(enter);
//        fallingSquaresTest(enter);
//        calcEquationTest(enter);
//        maxProductPathTest(enter);
        findElementsTest(enter);
    }


    /**********************************************private*************************************************/

    private static void findElementsTest(Enter enter) {
        TreeNode tree = createAll_1Tree(3);
        printLevel(tree);
        FindElements fe = new FindElements(tree);
        int[] targets = new int[]{1, 3, 8};
        for (int i = 0; i < targets.length; i++) {
            System.out.println(fe.find(targets[i]));
        }
    }


    private static void maxProductPathTest(Enter enter) {
        System.out.println(enter.maxProductPath(new int[][]{
                {2, 1, 3, 0, -3, 3, -4, 4, 0, -4},
                {-4, -3, 2, 2, 3, -3, 1, -1, 1, -2},
                {-2, 0, -4, 2, 4, -3, -4, -1, 3, 4},
                {-1, 0, 1, 0, -3, 3, -2, -3, 1, 0},
                {0, -1, -2, 0, -3, -4, 0, 3, -2, -2},
                {-4, -2, 0, -1, 0, -3, 0, 4, 0, -3},
                {-3, -4, 2, 1, 0, -4, 2, -4, -1, -3},
                {3, -2, 0, -4, 1, 0, 1, -3, -1, -1},
                {3, -4, 0, 2, 0, -2, 2, -4, -2, 4},
                {0, 4, 0, -3, -4, 3, 3, -1, -2, -2}
        }));
    }

    private static void calcEquationTest(Enter enter) {
        List<List<String>> equations = new ArrayList<>();
        equations.add(Arrays.asList("a", "b"));
        equations.add(Arrays.asList("e", "f"));
        equations.add(Arrays.asList("b", "e"));
        List<List<String>> queries = new ArrayList<>();
        queries.add(Arrays.asList("b", "a"));
        queries.add(Arrays.asList("a", "f"));
        queries.add(Arrays.asList("f", "f"));
        queries.add(Arrays.asList("e", "e"));
        queries.add(Arrays.asList("c", "c"));
        queries.add(Arrays.asList("a", "c"));
        queries.add(Arrays.asList("f", "e"));
        double[] answer = enter.calcEquation(equations, new double[]{3.4, 1.4, 2.3}, queries);
        System.out.println("answer:");
        for (double ans : answer) {
            System.out.printf("%.5f \n", ans);
        }
    }

    private static void fallingSquaresTest(Enter enter) {
        System.out.println(enter.fallingSquares(new int[][]{{9, 7}, {1, 9}, {3, 1}}));
    }

    private static void longestContinuousSubstringTest(Enter enter) {
        System.out.println(enter.longestContinuousSubstring("yrpjofyzubfsiypfre"));
    }

    private static void lengthAfterTransformationsTest(Enter enter) {
        System.out.println(enter.lengthAfterTransformations("cu", 5));
    }

    private static void detectCycleTest(Enter enter) {
        ListNode linked = createCycleLinked(4);
        print(enter.detectCycle(linked));
    }


    private static void reverseBetweenTest(Enter enter) {
        ListNode linked = createRandomLinked(5);
        print(linked);
        print(enter.reverseBetween(linked, 1, 3));
    }

    private static void partitionTest(Enter enter) {
        ListNode linked = createRandomLinked(6);
        enter.partition(linked, 25);
    }

    private static void rotateRightTest(Enter enter) {
        ListNode linked = createAscLinked(5, 1, 6, 1);
        print(linked);
//        print(enter.rotateRight(linked, 1));
        print(enter.rotateRight(linked, 2));
//        print(enter.rotateRight(linked, 3));
//        print(enter.rotateRight(linked, 4));
    }

    private static void reverseKGroupTest(Enter enter) {
        ListNode linked = createAscLinked(5, 1, 6, 1);
        print(linked);
        print(enter.reverseKGroup(linked, 3));
    }

    private static void deleteDuplicatesTest(Enter enter) {
        ListNode linked = createContainRepeatAscLinked(6, 0, 10, 2);
        print(linked);
        print(enter.deleteDuplicates(linked));
        ListNode linked2 = createAppointLinked(new int[]{0, 1, 2, 3, 3, 4, 4, 4, 5});
        ListNode linked3 = createAppointLinked(new int[]{1, 1, 2, 3, 3, 4, 4, 5});
        print(linked2);
        print(enter.deleteDuplicates(linked2));
        print(linked3);
        print(enter.deleteDuplicates(linked3));
    }

    private static void mergeKListsTest(Enter enter) {
        ListNode[] lists = new ListNode[4];
        ListNode link1 = createAscLinked(6, 0, 10, 2);
        ListNode link2 = createAscLinked(4, 0, 6, 1);
        ListNode link3 = createAscLinked(2, 0, 9, 1);
        ListNode link4 = createAscLinked(4, 0, 6, 3);
        print(link1);
        print(link2);
        print(link3);
        print(link4);
        lists[0] = link1;
        lists[1] = link2;
        lists[2] = link3;
        lists[3] = link4;
        print(enter.mergeKLists(lists));
    }

    private static void swapPairsTest(Enter enter) {
        ListNode linked = createAscLinked(4, 1, 4, 1);
        ListNode node = enter.swapPairs(linked);
        print(node);
    }

    private static void numTreesTest(Enter enter) {
        System.out.println(enter.numTrees(4));
    }

    /**********************************************function**********************************************/


    /**
     * 1261. 在受污染的二叉树中查找元素
     */
    static class FindElements {

        /*
        left : 2 * x + 1
        right : 2 * x + 2
         */
        private TreeNode dummy;
        private boolean isFlag = true;

        public FindElements(TreeNode root) {
            //root.var == 0
            //root var
            f1261(root, null, 0);
            printLevel(dummy);
        }

        private TreeNode f1261(TreeNode root, TreeNode p, int curVar) {
            if (Objects.isNull(root)) {
                return p;
            }
            p = new TreeNode(curVar);
            if (isFlag) {
                dummy = p;
                isFlag = false;
            }
            p.left = f1261(root.left, p.left, 2 * curVar + 1);
            p.right = f1261(root.right, p.right, 2 * curVar + 2);
            return p;
        }

        public boolean find(int target) {
            return dlr(dummy, target, false);
        }

        private boolean dlr(TreeNode dummy, int target, boolean isFlag) {
            if (Objects.isNull(dummy)) return isFlag;
            if (target == dummy.val) {
                isFlag = true;
                return true;
            }
            boolean left = dlr(dummy.left, target, isFlag);
            boolean right = dlr(dummy.right, target, isFlag);
            if (left || right) {
                return true;
            }
            return false;
        }
    }

    /**
     * 1594. 矩阵的最大非负积
     *
     * @param grid
     * @return
     */
    private long max = Long.MIN_VALUE;

    // todo
    public int maxProductPath(int[][] grid) {
        f1594(grid, 0, 0, 1);
        return max < 0 ? -1 : (int) (max % 1000000007);
    }

    private void f1594(int[][] grid, int i, int j, long product) {
        if (i == grid.length - 1 && j == grid[i].length - 1) {
            product *= grid[i][j];
            max = Math.max(product, max);
            return;
        }
        if (i < grid.length && j < grid[i].length) {
            product *= grid[i][j];
        } else {
            return;
        }
        // 向右
        f1594(grid, i, j + 1, product);
        // 向下
        f1594(grid, i + 1, j, product);
    }

    /**
     * 236. 二叉树的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (Objects.isNull(root) || Objects.equals(root, p) || Objects.equals(root, q)) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (Objects.nonNull(left) && Objects.nonNull(right)) {
            return root;
        }
        return Objects.isNull(left) ? right : left;
    }

    /**
     * 399. 除法求值
     *
     * @param equations
     * @param values
     * @param queries
     * @return
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // TODO
        Map<String, String> map = new HashMap<>();
        int count = 0;
        for (List<String> equation : equations) {
            String fz = equation.get(0);
            String fm = equation.get(1);
            double cs = values[count++];
            String value = fm + "-" + cs;
            map.put(fz, value);
            map.put(fm, fm);
        }
        double[] answer = new double[queries.size()];
        count = 0;
        for (List<String> query : queries) {
            String fz = query.get(0);
            String fm = query.get(1);
            double fzv = getFv(fz, map);
            double fmv = getFv(fm, map);
            double ans = fzv / fmv;
            answer[count++] = (ans < 0) || (fzv < 0) || (fmv < 0) ? -1 : ans;
        }
        return answer;
    }

    private double getFv(String f, Map<String, String> map) {
        double fv = 1;
        if (Objects.isNull(map.get(f))) return -1;
        while (!f.equals(map.get(f))) {
            String[] str = map.get(f).split("-");
            f = str[0];
            fv *= Double.valueOf(str[1]);
        }
        return fv;
    }


    /**
     * 3147. 从魔法师身上吸取的最大能量
     *
     * @param energy
     * @param k
     * @return
     */
    public int maximumEnergy(int[] energy, int k) {
        // TODO
        int max = Integer.MIN_VALUE, count = 0;
        int[] index = new int[k];
        for (int i = 0; i < k; i++) {
            int min = Integer.MAX_VALUE;
            index[i] = i;
            for (int j = i; j < energy.length; j += k) {
                if (energy[j] < min && energy[j] < 0) {
                    index[i] = j + k;
                    min = energy[j];
                }
            }
        }
        for (int i = 0; i < k; i++) {
            int tMax = energy[i] < energy.length ? 0 : Integer.MIN_VALUE;
            for (int j = index[i]; j < energy.length; j += k) {
                tMax += energy[j];
            }
            max = Math.max(tMax, max);
        }
        return max;
    }


    /**
     * 3216. 交换后字典序最小的字符串
     *
     * @param s
     * @return
     */
    public String getSmallestString(String s) {
        String[] strs = s.split("");
        for (int i = 1; i < strs.length; i++) {
            if ((Integer.parseInt(strs[i - 1]) & 1) == (Integer.parseInt(strs[i]) & 1)
                    && Integer.parseInt(strs[i]) < Integer.parseInt(strs[i - 1])) {
                String temp = strs[i];
                strs[i] = strs[i - 1];
                strs[i - 1] = temp;
                break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }

    TreeNode dummy;
    boolean flag = true;

    /**
     * 109. 有序链表转换二叉搜索树
     *
     * @param head
     * @return
     */
    public TreeNode sortedListToBST(ListNode head) {
        // TODO 可修改成快慢指针
        if (Objects.isNull(head)) return null;
        List<Integer> list = new ArrayList<>();
        while (Objects.nonNull(head)) {
            list.add(head.val);
            head = head.next;
        }
        int[] array = list.stream().mapToInt(Integer::intValue).toArray();
        f109(null, array, 0, array.length);
        return dummy;
    }

    private TreeNode f109(TreeNode root, int[] array, int start, int end) {
        if (start >= end) return root;
        int mid = start + ((end - start) >> 1);
        root = new TreeNode(array[mid]);
        if (flag) {
            dummy = root;
            flag = false;
        }
        root.left = f109(root.left, array, start, mid);
        root.right = f109(root.right, array, mid + 1, end);
        return root;
    }

    /**
     * 107. 二叉树的层序遍历 II
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (Objects.isNull(root)) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int loop = queue.size();
            List<Integer> t = new ArrayList<>(loop);
            for (int i = 0; i < loop; i++) {
                TreeNode first = queue.poll();
                t.add(first.val);
                if (Objects.nonNull(first.left)) {
                    queue.offer(first.left);
                }
                if (Objects.nonNull(first.right)) {
                    queue.offer(first.right);
                }
            }
            res.add(t);
        }
        Collections.reverse(res);
        return res;
    }

    /**
     * 275. H 指数 II
     *
     * @param citations
     * @return
     */
    public int hIndex(int[] citations) {
        // TODO
        int start = 0, end = citations.length - 1, len = citations.length, mid = start + ((end - start) >> 1);
        while (start < end) {
            mid = start + ((end - start) >> 1);
            int h = len - mid;
            if (citations[mid] >= h) {
                if (mid - 1 >= 0 && citations[mid - 1] < h) {
                    return h;
                } else {
                    end = mid - 1;
                }
            } else {
                start = mid + 1;
            }
        }
        return citations[mid] == 1 ? 1 : 0;
    }

    /**
     * 699. 掉落的方块
     *
     * @param positions
     * @return
     */
    public List<Integer> fallingSquares(int[][] positions) {
        // TODO 超内存
        List<Integer> ans = new ArrayList<>(positions.length);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < positions.length; i++) {
            int start = positions[i][0], side = positions[i][1], max = 0;
            Set<Integer> set = map.keySet();
            if (set.size() == 0) {
                max = side;
            } else {
                Set<Integer> collect = set.stream().filter(idx -> idx >= start && idx < start + side).collect(Collectors.toSet());
                for (Integer j : collect) {
                    max = Math.max(max, map.get(j));
                }
                max += side;
            }
            for (int j = start; j < start + side; j++) {
                map.put(j, max);
            }
            ans.add(Collections.max(map.values()));
        }
        return ans;
    }

    /**
     * 2414. 最长的字母序连续子字符串的长度
     *
     * @param s
     * @return
     */
    public int longestContinuousSubstring(String s) {
        int count = 0, idx = s.charAt(0), max = Integer.MIN_VALUE;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == idx++) {
                count++;
            } else {
                max = Math.max(max, count);
                count = 0;
                idx = s.charAt(i);
                i--;
            }
            if (max >= 26) return max;
        }
        return Math.max(max, count);
    }

    /**
     * 面试题 17.12. BiNode
     *
     * @param root
     * @return
     */
//    TreeNode dummy = new TreeNode(-1);
    TreeNode per = null;

    public TreeNode convertBiNode(TreeNode root) {
        ldr(root);
        return dummy.right;
    }

    private void ldr(TreeNode root) {
        if (Objects.isNull(root)) return;
        ldr(root.left);
        if (Objects.isNull(per)) {
            per = root;
            dummy.right = root;
        } else {
            per.right = root;
            per = root;
        }
        root.left = null;
        ldr(root.right);
    }


    /**
     * Q1. 数组的最大因子得分
     *
     * @param nums
     * @return
     */
    public long maxScore(int[] nums) {
        // TODO
        return 0L;
    }


    /**
     * Q2. 字符串转换后的长度 I
     *
     * @param s
     * @param t
     * @return
     */
    public int lengthAfterTransformations(String s, int t) {
        // TODO
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            int temp = s.charAt(i) - 96;
            temp += t;
            sum += Math.pow(2, temp / 26);
        }
        return sum;
//        List<Integer> list = new ArrayList<>();
//        for (int i = 0; i < s.length(); i++) {
//            list.add(s.charAt(i) - 96);
//        }
//        for (int i = 0; i < t; i++) {
//            int loop = list.size(), index = 0;
//            for (int j = 0; j < loop; j++) {
//                if (list.get(index) == 26) {
//                    list.remove(index);
//                    list.add(1);
//                    list.add(2);
//                } else {
//                    list.set(index, list.get(index) + 1);
//                    index++;
//                }
//            }
//        }
//        return list.size();
    }

    /**
     * 513. 找树左下角的值
     *
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        // TODO
        if (Objects.isNull(root)) return 0;
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int loop = queue.size();
            List<Integer> temp = new ArrayList<>(loop);
            for (int i = 0; i < loop; i++) {
                TreeNode first = queue.poll();
                temp.add(first.val);
                if (Objects.nonNull(first.left)) {
                    queue.add(first.left);
                }
                if (Objects.nonNull(first.right)) {
                    queue.add(first.right);
                }
            }
            result.add(temp);
        }
        return result.get(result.size() - 1).get(0);
    }

    /**
     * 103. 二叉树的锯齿形层序遍历
     *
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (Objects.isNull(root)) return new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int loop = queue.size();
            List<Integer> temp = new ArrayList<>(loop);
            for (int i = 0; i < loop; i++) {
                TreeNode first = queue.poll();
                temp.add(first.val);
                if (Objects.nonNull(first.left)) {
                    queue.add(first.left);
                }
                if (Objects.nonNull(first.right)) {
                    queue.add(first.right);
                }
            }
            result.add(temp);
        }
        for (int i = 1; i < result.size(); i += 2) {
            Collections.reverse(result.get(i));
        }
        return result;
    }

    /**
     * 98. 验证二叉搜索树
     *
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        return achieveFuncByIsValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean achieveFuncByIsValidBST(TreeNode root, long minValue, long maxValue) {
        if (Objects.isNull(root)) return true;
        if (root.val <= minValue || root.val >= maxValue) {
            return false;
        }
        return achieveFuncByIsValidBST(root.left, minValue, root.val) && achieveFuncByIsValidBST(root.right, root.val, maxValue);
    }

    /**
     * 496. 下一个更大元素 I
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            boolean flag = false;
            int value = -1;
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    flag = true;
                }
                if (flag && nums2[j] > nums1[i]) {
                    value = nums2[j];
                    break;
                }
            }
            result[i] = value;
        }
        return result;
    }

    /**
     * 142. 环形链表 II
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (Objects.isNull(head) || Objects.isNull(head.next)) return null;
        ListNode quick = head;
        ListNode slow = head;
        while (Objects.nonNull(quick) && Objects.nonNull(quick.next)) {
            quick = quick.next.next;
            slow = slow.next;
            if (Objects.equals(quick, slow)) break;
        }
        if (Objects.isNull(quick)) return null;
        quick = head;
        while (Objects.nonNull(quick)) {
            if (Objects.equals(quick, slow)) break;
            quick = quick.next;
            if (Objects.isNull(slow)) return null;
            slow = slow.next;
        }
        return quick;
    }

    /**
     * 92. 反转链表 II
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (Objects.isNull(head) || left == right) return head;
        ListNode dummy = new ListNode(-1, head), front = null, end = null, reverse = null, p = dummy;
        for (int i = 0; i < left - 1; i++) {
            p = p.next;
        }
        front = p;
        reverse = p.next;
        p = p.next;
        for (int i = 0; i < right - left; i++) {
            p = p.next;
        }
        if (Objects.nonNull(p)) {
            end = p.next;
            p.next = null;
        }
        ListNode node = reverseLinked(reverse);
        front.next = node;
        while (Objects.nonNull(node.next)) {
            node = node.next;
        }
        node.next = end;
        return dummy.next;
    }

    /**
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        ListNode sh = null, st = null, mh = null, mt = null;
        while (Objects.nonNull(head)) {
            if (head.val < x) {
                if (sh == null) {
                    sh = head;
                } else {
                    st.next = head;
                }
                st = head;
            } else {
                if (mh == null) {
                    mh = head;
                } else {
                    mt.next = head;
                }
                mt = head;
            }
            head = head.next;
        }
        if (mh != null) mt.next = null;
        if (sh == null) return mh;
        st.next = mh;
        return sh;
    }

    /**
     * 61. 旋转链表
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (Objects.isNull(head) || Objects.isNull(head.next) || k == 0) {
            return head;
        }
        ListNode dummy = new ListNode(-1, head), p = head;
        int count = 1;
        while (Objects.nonNull(p.next)) {
            p = p.next;
            count++;
        }
        p.next = head;
        for (int i = 0; i < count - (k % count); i++) {
            head = head.next;
            dummy = dummy.next;
        }
        dummy.next = null;
        return head;
    }

    /**
     * 25. K 个一组翻转链表
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (Objects.isNull(head)) return null;
        if (k == 1) return head;
        //辅助空间
        List<ListNode> list;
        ListNode dummy = new ListNode(-1), p = dummy;
        while (Objects.nonNull(head)) {
            list = new ArrayList<>(k);
            while (list.size() < k && Objects.nonNull(head)) {
                list.add(head);
                head = head.next;
            }
            //翻转
            if (Objects.nonNull(head) || list.size() == k) {
                for (int i = k - 1; i >= 0; i--) {
                    p.next = list.get(i);
                    p = p.next;
                }
            } else {
                for (int i = 0; i < list.size(); i++) {
                    p.next = list.get(i);
                    p = p.next;
                }
            }
        }
        p.next = null;
        return dummy.next;

        // TODO 不使用辅助空间
//        if (k == 1) return head;
//        ListNode dummy = new ListNode(-1, head), fast = dummy, slow = dummy;
//        while (Objects.nonNull(fast)) {
//            // 快的先走
//            for (int i = 0; i < k && Objects.nonNull(fast); i++) {
//                fast = fast.next;
//            }
////            if (Objects.isNull(fast)) break;
//            // 翻转
//            ListNode temp = fast;
//
//        }
    }

    /**
     * 82. 删除排序链表中的重复元素 II
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
//        //有辅助空间
//        if (Objects.isNull(head)) return null;
//        List<ListNode> list = new ArrayList<>();
//        list.add(head);
//        int per = head.val, index = -1;
//        head = head.next;
//        while (Objects.nonNull(head)) {
//            if (head.val == per) {
//                index = list.size() - 1;
//                head = head.next;
//                continue;
//            }
//            if (index >= 0) {
//                list.remove(index);
//                index = -1;
//            }
//            per = head.val;
//            list.add(head);
//            head = head.next;
//        }
//        if (index >= 0) {
//            list.remove(index);
//        }
//        for (int i = 1; i < list.size(); i++) {
//            list.get(i - 1).next = list.get(i);
//        }
//        if (list.size() > 0) {
//            list.get(list.size() - 1).next = null;
//            return list.get(0);
//        } else {
//            return null;
//        }

        // TODO 无辅助空间
        if (Objects.isNull(head) || Objects.isNull(head.next)) {
            return head;
        }
        ListNode dummy = new ListNode(-101, head), slow = dummy.next, fast = dummy.next, pre = dummy;
        while (Objects.nonNull(fast)) {
            //只快走
            if (fast.hashCode() == slow.hashCode() || fast.val == slow.val) {
                fast = fast.next;
            } else {
                slow.next = fast;
                slow = slow.next;
                pre.next = slow;
            }
        }
        return dummy.next;
    }


    /**
     * 24. 两两交换链表中的节点
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if (Objects.isNull(head)) {
            return null;
        }
        if (Objects.isNull(head.next)) {
            return head;
        }
        ListNode dummy = new ListNode(0, head), t = dummy;
        while (Objects.nonNull(head) && Objects.nonNull(head.next)) {
            t.next = head.next;
            t = t.next;
            head.next = head.next.next;
            t.next = head;
            t = t.next;
            head = head.next;
        }
        return dummy.next;
//        if (Objects.isNull(head)) {
//            return null;
//        }
//        if (Objects.isNull(head.next)) {
//            return head;
//        }
//        List<ListNode> list = new ArrayList<>();
//        while (Objects.nonNull(head)) {
//            list.add(head);
//            head = head.next;
//        }
//        for (int i = 1; i < list.size(); i += 2) {
//            ListNode temp = list.get(i);
//            list.set(i, list.get(i - 1));
//            list.set(i - 1, temp);
//        }
//        list.get(list.size() - 1).next = null;
//        for (int i = 1; i < list.size(); i++) {
//            list.get(i - 1).next = list.get(i);
//        }
//        return list.get(0);
    }

    /**
     * 96. 不同的二叉搜索树
     *
     * @param n
     * @return
     */
    public int numTrees(int n) {
        //TODO
        int sum = 0;

        return sum;
    }

    /**
     * 合并 K 个升序链表
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (Objects.isNull(lists)) return null;
        int count = lists.length, min;
        boolean[] flags = new boolean[lists.length];
        ListNode dummy = new ListNode(0), t = dummy;
        min = findMin(lists);
        while (count > 0) {
            for (int i = 0; i < lists.length; i++) {
                if (!flags[i] && Objects.isNull(lists[i])) {
                    count--;
                    flags[i] = true;
                    continue;
                }
                if (Objects.nonNull(lists[i]) && lists[i].val == min) {
                    t.next = new ListNode(min);
                    t = t.next;
                    lists[i] = lists[i].next;
                }
            }
            min = findMin(lists);
        }
        return dummy.next;
    }

    private int findMin(ListNode[] lists) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < lists.length; i++) {
            if (Objects.nonNull(lists[i])) {
                min = Math.min(min, lists[i].val);
            }
        }
        return min;
    }

    /**
     * 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode quick = head, slow = head;
        for (int i = 0; i < n; i++) {
            quick = quick.next;
        }
        if (Objects.isNull(quick)) {
            return head.next;
        }
        while (Objects.nonNull(quick.next)) {
            quick = quick.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }

    /**
     * 794. 有效的井字游戏
     *
     * @param board
     * @return
     */
    public boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                xCount = (c == 'X') ? (xCount + 1) : xCount;
                oCount = (c == 'O') ? (oCount + 1) : oCount;
            }
        }
        return !((oCount != xCount && oCount != xCount - 1) ||
                (oCount != xCount - 1 && win(board, 'X')) ||
                (oCount != xCount && win(board, 'O')));
    }

    public boolean win(String[] board, char p) {
        for (int i = 0; i < 3; ++i) {
            if ((p == board[0].charAt(i) && p == board[1].charAt(i) && p == board[2].charAt(i)) ||
                    (p == board[i].charAt(0) && p == board[i].charAt(1) && p == board[i].charAt(2))) {
                return true;
            }
        }
        return ((p == board[0].charAt(0) && p == board[1].charAt(1) && p == board[2].charAt(2)) ||
                (p == board[0].charAt(2) && p == board[1].charAt(1) && p == board[2].charAt(0)));
    }


    /**
     * 2684. 矩阵中移动的最大次数
     *
     * @param grid
     * @return
     */
//    private int max = 0;

//    public int maxMoves(int[][] grid) {
//        // TODO 未完成
//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[i].length; j++) {
//                achieveFuncByMaxMoves(grid, i, j, 0);
//            }
//        }
//        return max;
//    }
    private void achieveFuncByMaxMoves(int[][] grid, int row, int col, int current) {
        //上
        if (row - 1 >= 0 && col + 1 < grid[row - 1].length) {
            if (grid[row - 1][col + 1] <= grid[row][col]) {
                max = Math.max(current, max);
            } else {
                achieveFuncByMaxMoves(grid, row - 1, col + 1, current++);
            }
        }
        //中
        if (col + 1 < grid[row].length) {
            if (grid[row][col + 1] <= grid[row][col]) {
                max = Math.max(current, max);
            } else {
                achieveFuncByMaxMoves(grid, row, col + 1, current++);
            }
        }
        //下
        if (row + 1 < grid.length && col + 1 < grid[row + 1].length) {
            if (grid[row + 1][col + 1] <= grid[row][col]) {
                max = Math.max(current, max);
            } else {
                achieveFuncByMaxMoves(grid, row + 1, col + 1, current++);
            }
        }
    }

    /**
     * 2566. 替换一个数字后的最大差值
     *
     * @param num
     * @return
     */
    public int minMaxDifference(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int max = achieveFuncByMinMaxDifference(chars, '9');
        int min = achieveFuncByMinMaxDifference(chars, '0');
        return max - min;
    }

    /**
     * 子函数 - 替换一个数字后的最大差值
     *
     * @param chars
     * @param flag
     * @return
     */
    private int achieveFuncByMinMaxDifference(char[] chars, char flag) {
        StringBuilder sb = new StringBuilder();
        //找到第一个非flag
        int i;
        for (i = 0; i < chars.length; i++) {
            if (chars[i] != flag) break;
            sb.append(chars[i]);
        }
        for (int j = i; j < chars.length; j++) {
            if (chars[j] == chars[i]) sb.append(flag);
            else sb.append(chars[j]);
        }
        return Integer.parseInt(sb.toString());
    }

    /**
     * 71. 简化路径
     *
     * @param path
     * @return
     */
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String[] dir = path.split("/");
        for (String s : dir) {
            if (s.equals(".") || s.equals("") || s.equals(" ")) continue;
            else if (s.equals("..")) {
                if (stack.size() != 0) stack.pop();
            } else stack.push(s);
        }
        String[] target = new String[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            String top = stack.pop();
            target[i] = top;
        }
        StringBuilder sb = new StringBuilder();
        for (String s : target) {
            sb.append("/").append(s);
        }
        if (sb.length() == 0) sb.append("/");
        return sb.toString();
    }
}
